package com.whitedust.top40;

import com.whitedust.structure.TreeNode;

/**
 * @author A
 * @since 2025/11/5 10:36
 */

public class Top33 {
    private int res = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        postOrder(root);
        return res;
    }

    private int postOrder(TreeNode root) {
        if (root == null) return 0;
        //取最大值的目的是为了保证左右两边在计算该节点时都是最优值
        int left = Math.max(postOrder(root.left), 0);
        int right = Math.max(postOrder(root.right), 0);
        //核心在于每个节点都处理一次，处理时也只需要考虑包括此节点的情况
        int cur = left + right + root.val;
        //树的最大值在此节点来进行比较
        res = Math.max(res, cur);
        //此处应该返回的是该节点所对应的最大值，也就是包含该节点的最大值
        return root.val + Math.max(left, right);
    }
}
